In computer graphics, bits are stored in memory to represent coordinates in the display plane. A line segment in the display is formed by a number of discrete points. Currently, a line is calculated by means of the parameters determined from the line equation according to the Bresenham's algorithm. The disadvantage of this method is that one has to calculate each point in succession and the number of calculations is proportional to the length of the line. The basic operation of the Bresenham's algorithm is illustrated in FIG. 1 and the calculation shown below for a line between the points (0,0) and (40,6) in plane coordinate. The following sets of parameters and equations are used:
______________________________________ Let X = (40 - 0) = 40, and Y = (6 - 0) = 6. Define D = 2Y - X = -28, and D1 - 2Y = 12, and D2 = 2(Y - X) = -68. If D &lt; 0, then D becomes D + D1 and Y becomes Y + 0. If D .gtoreq. 0, then D becomes D + D2 and Y becomes Y + 1. ______________________________________
X is incremented by 1 in each series of calculations. In total, the calculation must be performed 40 times.
The results of the calculation are shown in Table 1 and FIG. 2.
TABLE 1 ______________________________________ Pixel Co- Length of Parameter Values ordinates Segment Where Y D D1 D2 X Y is Fixed Value ______________________________________ -28 12 -68 0 0 -16 12 -68 1 0 4 -4 12 -68 2 0 +8 12 -68 3 0 (D .gtoreq. 0) -60 12 -68 4 1 -48 12 -68 5 1 6 -36 12 -68 6 1 -24 12 -68 7 1 -12 12 -68 8 1 0 12 -68 9 1 (D .gtoreq. 0) -68 12 -68 10 2 -56 12 -68 11 2 7 -44 12 -68 12 2 -32 12 -68 13 2 -20 12 -68 14 2 -8 12 -68 15 2 +4 12 -68 16 2 (D .gtoreq. 0) -64 12 -68 17 3 -52 12 -68 18 3 7 -40 12 -68 19 3 -28 12 -68 20 3 -16 12 -68 21 3 -4 12 -68 22 3 +8 12 -68 23 3 (D .gtoreq. 0) -60 12 -68 24 4 -48 12 -68 25 4 6 -36 12 -68 26 4 -24 12 -68 27 4 -12 12 -68 28 4 0 12 -68 29 4 (D .gtoreq. 0) -68 12 -68 30 5 -56 12 -68 31 5 7 -44 12 -68 32 5 -32 12 -68 33 5 -20 12 -68 34 5 -8 12 -68 35 5 +4 12 -68 36 5 (D .gtoreq. 0) -64 12 -68 33 6 -52 12 -68 38 6 4 -40 12 -68 39 6 -28 12 -68 40 6 END ______________________________________
The above table illustrates the complexity of the process where Bresenham's algorithm is used. It is apparent that the longer the length of the line, the longer time the process takes.